Theorie der Formale Sprachen
Einführung
Formale Sprachen sind künstliche Sprachen, die es Computern ermöglichen, Daten und Informationen zu verarbeiten. Eine formale Sprache L besteht aus einer Menge von Wörtern, die wiederum aus Zeichen des Alphabets ∑ der Sprache bestehen.
Das Alphabet ist hierbei die Menge der Zeichen, die in einem Wort benutzt werden dürfen, wie zum Beispiel die Buchstaben von A bis Z und die Umlaute im deutschen Alphabet. Aber es können beliebige Symbole verwendet werden.
Grammatik
Formale Grammatiken beschreiben und erzeugen durch Symbole und Regeln formale Sprachen. Die Regeln definieren dabei, wie neue Symbole aus bereits bestehenden entstehen können. Bei den Symbolen unterscheidet man zwischen terminalen und nichtterminalen Symbolen. Nichtterminale Symbole können durch andere Symbole ersetzt werden, während terminale Symbole unveränderlich sind. Das heißt, man erkennt die Symbole an sogenannten Produktionsregeln. Diese Regeln beschreiben, aus welchen Zeichen welche anderen Zeichen entstehen können.
Man unterscheidet Grammatiken anhand der möglichen Einschränkungen ihrer Produktionsregeln. Die sogenannte Chomsky-Hierarchie stellt eine Hierarchie von Klassen formaler Grammatiken dar, welche formale Sprachen erzeugen. Darin werden vier verschiedene Arten von Typ-0 bis Typ-3 unterschieden, wobei Typ-0 die Sprache überhaupt nicht einschränkt, während Typ-3 die Grammatik sehr stark einschränkt.
Reguläre Grammatiken und Endliche Automaten
Die Reguläre Grammatik stellt eine Typ 3 Grammatik der Chomsky-Hierarchie dar und erzeugt reguläre Sprachen. Es ist ein 4-Tupel, bestehend aus der Menge der Terminalsymbole, der Nichtterminale und der Produktionen, sowie einem Startsymbol.
Die Grammatik wird über dieses 4-Tupel erzeugt:
G = (N, T, P, S)
N ist die Menge der Nichtterminale T={X,Y,Z}
T bezeichnet die Menge der Terminale T={a,b,c}
P beschreibt die Menge der Produktionsregeln
S bezeichnet das Startsymbol
Die Definition beschreibt somit zum einen die Grundelemente der Sprache, also Terminalsymbole, die beispielsweise bei Programmiersprachen für Schlüsselworte stehen. Aus diesen können dann Sätze zusammengestellt werden, die auf Produktionsregeln, bzw. Konstruktionsregeln basieren.
Beispiel um das Funktionsprinzip zu zeigen
Reguläre Grammatiken erzeugen reguläre Sprachen, deshalb gibt es für jede reguläre Sprache immer mindestens eine reguläre Grammatik. Zur besseren Verständlichkeit betrachten wir die folgende Sprache als Grammatik Beispiel“: $$ L = \{0^n1^{2m}|n>0, m\ge0 \}$$ Sie enthält alle Wörter, die mit einem bis n Nullen beginnen und mit keiner oder einer geraden Anzahl Einsen enden. Wenn man diese Sprache auf eine wie eben beschriebene reguläre Grammatik zurückführen kann, d.h. Produktionsregeln beschreiben, die genau die Art von Ausdrücken erzeugen, dann handelt es sich um eine reguläre Sprache. <\p>
Gestartet wird mit dem Startsymbol S. Dabei wird versucht zunächst das kleinstmögliche Wort zu bilden. Das wäre einfach Null. $$ S \rightarrow 0 $$ Mit der ersten Produktionsregel „S wird umgewandelt in Null“ bekommt man genau dieses Wort. Man benötigt aber eine Möglichkeit mehr als eine 0 zu erzeugen. Das gelingt, indem an die Null einfach erneut das Startsymbol angefügt wird: $$ S \rightarrow 0 S $$ Nachdem eine Null erzeugt wird, befindet man sich wieder im Zustand S und kann dadurch beliebig viele Nullen erzeugen. Im nächsten Schritt muss man das Wort entweder beenden oder mit den Einsen anfangen. Dabei kann man die Produktionsregel einfach erweitern: $$ S \rightarrow 0 S \; \big \vert \;1 S \;\big \vert \; \epsilon $$ Mit dieser Regel kann man das leere Wort erzeugen. Oder eines, das direkt mit einer 1 beginnt. Beides darf in der Sprache L aber nicht passieren. Deshalb muss zwischen dem Teil des Wortes, das Nullen enthält und dem Rest unterschieden werden. Dafür braucht man eine weitere Variable , auch Nonterminal Symbol genannt. $$ S \rightarrow 0 S \; \big \vert \;0 B $$ Mit dieser Regel können beliebig viele Nullen erzeugt werden, dabei muss aber mindestens eine erzeugt werden, bevor man sich dem nächsten Teil des Wortes in B widmen kann. Von B aus beendet man entweder mit Epsilon oder erzeugt Einsen: $$ B \rightarrow 1 B \; \big \vert \; \epsilon $$ Wenn ein Wort Einsen besitzt, müssen diese laut Definition in gerader Anzahl vorhanden sein. Dies wird mit einer Schleife erreicht. Dazu benötigt man eine weitere Variable C. Mit nachfolgender Regel gelangt man von B mit einer 1 nach C und von dort mit einer weiteren 1 nach B zurück. $$ B \rightarrow 1 C \; \big \vert \; \epsilon $$ $$ C \rightarrow 1 B $$ Zusammengefasst haben wir dann folgende Produktionsregeln, die die Sprache L erzeugen: $$ \begin{align*} S &\rightarrow 0 S \\ S &\rightarrow 0 S \; \big \vert \;1 S \;\big \vert \; \epsilon \\ S &\rightarrow 0 S \; \big \vert \;0 B \\ B &\rightarrow 1 B \; \big \vert \; \epsilon \\ B &\rightarrow 1 C \; \big \vert \; \epsilon \\ C &\rightarrow 1 B \end{align*} $$ Auf diese Weise können komplexe Sprachen definiert und maschinell erkannt werden.
Endliche Automaten
Ein endlicher Automat ist ein mathematisches Modell zur Verarbeitung von Eingaben (z. B. Zeichenketten). Er besteht aus:<\p>
- Einer endlichen Menge von Zuständen
- Einem Startzustand
- Einer Menge akzeptierender Endzustände
- Einer Übergangsfunktion, die bestimmt, wie der Automat auf Eingaben reagiert
Man unterscheidet dabei zwei Untertypen: Deterministische (DEA) und Nichtdeterministische (NEA)Automaten. Deterministische endliche Automaten erzeugen für jeden Zustand und jedes Eingabesymbol genau einen Folgezustand. Die Übergangsfunktion ist dabei eindeutig.
Ein NEA erlaubt dagegen mehrere mögliche Übergänge für dieselbe Eingabe im selben Zustand. Es kann auch keinen Übergang geben (d.h. der Automat kann „stecken bleiben“) und „ε“-Übergänge (Übergänge ohne Eingabezeichen) sind ebenfalls möglich. Beide Automaten erkennen die selben Sprache-Klassen.
Arbeitsweise eines DEA-Automaten
Die Arbeitsweise eines DEA ist hierbei so simpel wie genial: Nehmen wir an, es liegt ein Eingabewort vor, das nur aus Zeichen des Eingabealphabets besteht. Der Automat startet nun in seinem Startzustand, den wir hier $Z_0$ nennen. Nun liest der Automat das erste Zeichen des Wortes ein, wodurch sich der Zustand des Automaten ändert. Dafür brauchen wir die Übergangsfunktion: Der Automat betrachtet den aktuellen Zustand $Z_0$ und das eingelesene Zeichen. Er erfährt durch die Übergangsfunktion den neuen Zustand, beziehungsweise den Folgezustand. Dies geschieht so lange, bis das Wort vollständig eingelesen ist. Befindet sich der Automat nun in einem Endzustand, dann wird das Eingabewort akzeptiert. Ist der Automat jedoch in einem normalen Zustand, wird das Wort verworfen.
Zustandsübergangsdiagramm zum erkennen von Telefonnummern
Ein Zustandsdiagramm ist eine grafische Darstellung eines Zustandsautomaten. Es zeigt, wie ein System oder Objekt auf Ereignisse reagiert und dabei von einem Zustand in einen anderen übergeht. Zustandsdiagramme sind extrem nützlich, wenn es darum geht, das Verhalten eines Systems zu formal zu beschreiben oder zu dokumentieren. Sie zeigen,System auf Ereignisse reagiert und dabei von einem Zustand in einen anderen übergeht.
Die Funktion soll am Beispiel eiens AUtomaten der einfache Telefon-Nummern erkennt erklärt werden. Aufgabe ist es Telefon-Nummern der Form 089/216789 oder 040-985423 zu erkennen. Es ist bewusst auf internationale Nummern Erkennung verzichtet worden. Wichtig ist dass der Automat berücksichtigt dass nach der Vorwahl keine "0" mehr erlaubt ist. Als regulärer Ausdruck würde das so aussehen:
0[1-9][0-9]*[/-][1-9][0-9]*
Der Ausdruck erlaubt : 089-1234567 oder auch 07101-321786 und lehnt 089/012345 ab
Die Syntax, die zur Beschreibung der regulären Ausdrücken verwendet wird, wie ?, *, +, () usw. gehört zur sogenannten Regex-Syntax – kurz für Regular Expressions. Diese Syntax ist ein standardisiertes System zur Beschreibung von Mustererkennung in Zeichenketten.
Beispiel wie eine Grammatik für internationale Telefonnummer als regulärer Ausdruck in Regex-Systax formuliert werden kann:
(?:\+49|0049|0)\s?(?:\(?[1-9][0-9]{1,4}\)?)[\s/\-]?[1-9][0-9]{2,}[\-]?[0-9]{0,4}
Das würde aber den Rahmen dieser Einführung etwas überdehnen. Daher konzentrieren wir uns auf eine einfachere Form, um die Zusammenhänge deutlich zu machen. Zurück zu unserem Beispiel. Ein entsprechendes Zustandsübergangsdiagramm für die Erkennung der einfachen telefon-nummern sieht so aus:
Die Funktionsweise lässt sich wie folgt beschreiben. Ausgehend vom Startzustand "0" wird in Abhängigkeit des gelesenen Symbols (Eingabe-Zeichen) von Zustand zu Zustand übergegangen. Gelangt man zum Endzustand (4) liegt ein gemäß der Grammatik gültiges Wort oder Ausdruck vor. Landet man im Zustand 5 (Fehler-Zustand) wurde kein gültiger Ausdruck erkannt.
Zustand 0:
Eingabe 0 → Zustand 1
Eingabe 1–9 → Zustand 5 (Fehler)
Eingabe / - oder sonst → Zustand 5
Zustand 1:
Eingabe 1–9 → Zustand 2
Eingabe 0 → Zustand 6
Eingabe / - oder sonst → Zustand 5
Zustand 2:
Eingabe 0–9 → Zustand 2
Eingabe / - → Zustand 3
Eingabe sonst → Zustand 5
Zustand 3:
Eingabe 1–9 → Zustand 4
Eingabe 0 → Zustand 5
Eingabe / - oder sonst → Zustand 5
Zustand 4:
Eingabe 0–9 → bleibt in Zustand 4
Eingabe / - oder sonst → Zustand 5
Zustand 5: Fehlerzustand → bleibt dort bei jeder Eingabe
Übertragung in Programmcode
Ein wesentlicher Vorteil von EA ist das man diese sehr effizient in Programmcode überführen kann. Im folgenden ist das am Beispiel der Telefon-Nummern Erkennung dargestellt:
# Python Programm zum testen des regulären Automaten
import re
def ist_gueltige_telefonnummer(nummer: str) -> bool:
muster = r"^0[1-9][0-9]*[/\-][1-9][0-9]*$"
return re.fullmatch(muster, nummer) is not None
# Testfälle
testnummern = [
"089/1234567", # ✅ gültig
"0123-456789", # ✅ gültig
"0123/0456789", # ❌ ungültig (Teil nach / beginnt mit 0)
"123/456789", # ❌ ungültig (beginnt nicht mit 0)
"089A1234567", # ❌ ungültig (Buchstabe)
"089/123-4567", # ❌ ungültig (zweites Trennzeichen)
]
for nummer in testnummern:
print(f"{nummer}: {'gültig' if ist_gueltige_telefonnummer(nummer) else 'ungültig'}")
Eine etwas andere Variante zeigt, wie man basierend auf der Zustandsübergangs-Matrix eine sogenannte Final State Maschine (FSM) implementieren kann. Derartige FSM können für unterschiedlichste Anwendungen bei denen es um komplexere Entscheidungs-Findungen geht angewendet werden.
Wir bauen für den Arduino
- Ein enum für die Menge von Zuständen
- Eine Funktion zur Zustandsübergabe
- Eine Funktion zur Prüfung, ob die Eingabe gültig ist
- Ein Beispiel-Setup, das leicht erweitert werden kann
char fsm[6][7] = {
{1,5,2,5,4,5,5}, // Z0
{5,2,2,5,4,5,5}, // Z1
{5,5,3,5,5,5,5}, // Z2
{5,5,5,5,5,5,5}, // Z3
{5,5,5,5,5,5,5}, // Z4 (Endzustand → keine Übergänge)
{5,5,5,5,5,5,5} // Z5 (Fehlerzustand → bleibt im Fehler)
};
enum Zustand {
Z0, Z1, Z2, Z3, Z4, Z5, Z6
};
//----------Übergangslogik-------------------------------------
Zustand naechsterZustand(Zustand aktueller, char eingabe) {
switch (aktueller) {
case Z0:
if (eingabe == '0') return Z1;
else return Z5;
case Z1:
if (eingabe >= '1' && eingabe <= '9') return Z2;
else if (eingabe == '0') return Z6;
else return Z5;
case Z2:
if (eingabe >= '0' && eingabe <= '9') return Z2;
else if (eingabe == '/' || eingabe == '-') return Z3;
else return Z5;
case Z3:
if (eingabe >= '1' && eingabe <= '9') return Z4;
else return Z5;
case Z4:
if (eingabe >= '0' && eingabe <= '9') return Z4;
else return Z5;
case Z6:
return Z5;
default:
return Z5;
}
}
//------Validierungsfunktion------------------------------
bool istGueltigeTelefonnummer(const char* nummer) {
Zustand zustand = Z0;
for (int i = 0; nummer[i] != '\0'; i++) {
zustand = naechsterZustand(zustand, nummer[i]);
if (zustand == Z5) return false;
}
return zustand == Z4;
}
//------Beispiel------------------------------
// Anzahl der Zustände und Eingabeklassen
const int ZUSTANDSZAHL = 6;
const int KLASSENZAHL = 7;
// Zustände: Z0 = Start, Z4 = Endzustand, Z5 = Fehler
// FSM-Matrix: [aktueller Zustand][Eingabeklasse] = nächster Zustand
int fsm[ZUSTANDSZAHL][KLASSENZAHL] = {
// 0 1–9 Ziff / - ' ' sonst
{ 1, 5, 2, 5, 4, 5, 5 }, // Z0
{ 5, 2, 2, 5, 4, 5, 5 }, // Z1
{ 5, 5, 3, 5, 5, 5, 5 }, // Z2
{ 5, 5, 5, 5, 5, 5, 5 }, // Z3
{ 5, 5, 5, 5, 5, 5, 5 }, // Z4 (Endzustand)
{ 5, 5, 5, 5, 5, 5, 5 } // Z5 (Fehlerzustand)
};
// 🧠 Eingabeklasse bestimmen
int eingabeKlasse(char c) {
if (c == '0') return 0;
if (c >= '1' && c <= '9') return 1;
if (c >= '0' && c <= '9') return 2;
if (c == '/') return 3;
if (c == '-') return 4;
if (c == ' ') return 5;
return 6; // Sonstiges
}
// 🔁 FSM ausführen
bool istGueltigeTelefonnummer(String eingabe) {
int zustand = 0; // Startzustand Z0
for (int i = 0; i < eingabe.length(); i++) {
int klasse = eingabeKlasse(eingabe[i]);
zustand = fsm[zustand][klasse];
if (zustand == 5) return false; // Fehlerzustand
}
return (zustand == 4); // Endzustand Z4
}
// 🖥️ Setup: Serielle Kommunikation starten
void setup() {
Serial.begin(9600);
Serial.println("📞 FSM-Telefonnummern-Erkenner gestartet.");
Serial.println("Gib eine Telefonnummer ein (z. B. 089/123456):");
}
// 🔄 Loop: Eingabe lesen und prüfen
void loop() {
if (Serial.available()) {
String eingabe = Serial.readStringUntil('\n');
eingabe.trim(); // Leerzeichen am Anfang/Ende entfernen
Serial.print("Eingabe: ");
Serial.println(eingabe);
if (istGueltigeTelefonnummer(eingabe)) {
Serial.println("✅ Gültige Telefonnummer erkannt!");
} else {
Serial.println("❌ Ungültige Telefonnummer.");
}
Serial.println("\nGib eine neue Nummer ein:");
}
}